It is well known that digital data transmitted over a communications channels is subject to signal impairments created by noise, distortion and fading, creating transmission errors. These types of errors can also occur when digital data is stored on devices, including magnetic media or solid-state memories that contain imperfections. This noise is critical in wireless communications where the noise can be extensive and the amount of power used in communication is limited. Typically, the noisy channel is characterized by the signal-to-noise ratio (SNR), which is a ratio of the signal energy over the noise energy in decibels. It is also possible to take the difference in transmission rates into account and define the SNR per bit when the efficiency of codes is compared with different code rates.
It is known that introducing a controlled amount of redundancy by coding in a selected message before a transmission over a communications channel corrects possible errors due to noise, as noted by Dr. Claude Shannon. In a noisy channel, the transmission rate is reduced to obtain accuracy. A limit, called the Shannon limit, shows the upper bound of the transmission rate for lossless communications in a noisy channel.
Block codes were first used in communications, but these block codes were not efficient when comparing to the Shannon limit. More efficient channel codes have been developed on the basis of trellis coding. A trellis encoder includes a Finite State Machine (FSM) and typically a signal mapper. The trellis is generated by the FSM, while code words are binary sequences that are one-to-one mappings of all distinct paths on the trellis by the signal mapper. When a special input sequence is transmitted, the path corresponding to this input sequence is found on the trellis, and the code word generated by the signal mapper. On the decoding side, a maximum likelihood (ML) decoder as a Viterbi decoder or a Maximum a Posteriori (MAP) decoder converts the received code words into the input sequence.
One important parameter of the Finite State Machine is the memory length m that decides the trellis. The most widely used trellis codes include convolutional codes and turbo codes, as noted in many teachings, including the IEEE technical paper entitled, “Modulation Encoding For Linear Gaussian Channels,” IEEE Transactions on Information Theory, Volume 44, No. 6, October 1998, the disclosure which is hereby incorporated by reference in its entirety.
Other examples of trellis coding, the use of convolutional codes, and convolutional encoders are disclosed in U.S. Pat. Nos. 5,706,312; 6,108,374; 6,215,827 assigned to Lucent Technologies; and 6,347,122 assigned to Agere Systems, the disclosures which are hereby incorporated by reference in their entirety.
As is known to those skilled in the art, trellis coded modulation is a combined method for joint coding and modulation based on the design of convolutional codes. These are matched to a modulation signal, which is established to maximize the Euclidian distance between a modulated sequence. A trellis diagram is a graph that represents the changing time of a Finite State Machine by defining the states as vertices. Any possible state transitions are displayed as edges. As to the various types of codes, a convolutional code is generated by a linear shift-register circuit and performs a convolution operation on an information sequence, while a turbo code is generated by a parallel concatenation of two (or more) simple convolutional encoders that are separated by interleavers. Thus, along the lines of a turbo code, a concatenated code is established cascading two codes separated by an interleaver. In a generator matrix, a K×N matrix produces a code word (of length N) of a block code by multiplying the information block of length K. The hamming distance is the number of places in which two sequences of equal length differ. The minimum distance of a code is the smallest hamming distance between any pair of code words. The weight distribution is a list of the hamming distances of each code word from a given reference code word.
A Viterbi algorithm is an efficient method for decoding convolutional codes based on finding the path on a trellis diagram that is at a minimum distance from a receive sequence. Related to Viterbi coding is Maximum-Likelihood (ML) decoding that maximizes the probability of a receive sequence given any of the possible code words. If code words are equally likely, there could be minimum possible error probability.
A convolutional code has been used in GSM and IS-95 systems. Its signal mapper consists of code word generators that define the addition and multiplication on the finite algebra. It is not efficient in comparison of its results to the Shannon limit. Its efficiency would be increased as the memory m increases. Both the computational complexity and memory storage for the Viterbi decoder will be doubled as m increases one. Thus, this approach is not feasible even for m=20. Turbo code, as noted before, is a further development of the convolutional code using parallel concatenation of two or more of the convolutional encoders and a pseudo-random interleaver. This code system allows a user to transfer the information in a noisy channel almost without distortion by a rate close to the Shannon limit. Unfortunately, it has a longer delay than that delay used with the conventional convolutional code. In any event, both convolutional codes and turbo codes are recommended in the third generation wireless communication systems, similar to UMTS and CDMA 2000.